﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEuler.Sudoku
{
    public sealed class SudokuBacktrackingSolver : SudokuSolver
    {
        private readonly HashSet<Int32>[] _rows;
        private readonly HashSet<Int32>[] _regions;
        private readonly HashSet<Int32>[] _columns;

        public SudokuBacktrackingSolver(SudokuPuzzle puzzle)
            : base(puzzle)
        {
            _columns = MakeHashSets(puzzle.Size);
            _regions = MakeHashSets(puzzle.Size);
            _rows = MakeHashSets(puzzle.Size);
        }

        public override Boolean TryFindSolution()
        {
            SetupCaches();
            return Try(0);
        }

        private Boolean Try(Int32 current)
        {
            var node = Puzzle.FreeNodes[current];

            for (var i = 1; i <= Puzzle.Size; i++)
            {
                if (Try(node, i))
                {
                    if (current == (Puzzle.FreeNodes.Count - 1))
                    {
                        return true;
                    }

                    if (Try(current + 1))
                    {
                        return true;
                    }

                    Undo(node, i);
                }
            }

            return false;
        }

        private Boolean Try(SudokuNode node, Int32 i)
        {
            var col = _columns[node.Column];
            var reg = _regions[node.Region];
            var row = _rows[node.Row];

            if (reg.Contains(i) || col.Contains(i) || row.Contains(i))
            {
                return false;
            }

            col.Add(i);
            reg.Add(i);
            row.Add(i);

            node.Value = i;
            return true;
        }

        private void Undo(SudokuNode node, Int32 i)
        {
            node.Value = 0;

            _columns[node.Column].Remove(i);
            _regions[node.Region].Remove(i);
            _rows[node.Row].Remove(i);
        }

        private void SetupCaches()
        {
            for (int y = 0; y < Puzzle.Size; y++)
            {
                for (int x = 0; x < Puzzle.Size; x++)
                {
                    var n = Puzzle[y, x];

                    if (n.IsFixed)
                    {
                        _columns[n.Column].Add(n.Value);
                        _regions[n.Region].Add(n.Value);
                        _rows[n.Row].Add(n.Value);
                    }
                }
            }
        }

        private static HashSet<Int32>[] MakeHashSets(Int32 count)
        {
            var result = new HashSet<Int32>[count];

            for (int i = 0; i < count; i++)
            {
                result[i] = new HashSet<Int32>();
            }

            return result;
        }
    }
}
